package 第10周_冒泡排序_希尔排序和排序算法.第2章_希尔排序;

import 第1周_线性查找法.测试算法性能.ArrayGenerator;
import 第2周_排序基础.第一章选择排序法.SortingHelper;

import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Queue;

/**
 * 希尔排序
 */
public class ShellSort {

    private ShellSort(){}

    public static <E extends Comparable<E>> void sort(E[] data){

        int h = data.length / 2;
        while (h >= 1){

            //start为每一个子数组起始的那个元素索引
            for (int start = 0; start < h; start++){
                //data[start, start + h, start + 2h]
                //从这个子数组的第二个元素开始看
                for (int i = start + h; i < data.length; i+=h){
                    E t = data[i];
                    int j;
                    for (j = i; j - h >= 0 && t.compareTo(data[j - h]) < 0; j -= h){
                        data[j] = data[j - h];
                    }
                    data[j] = t;
                }
            }
            h /= 2;
        }
    }


    public static <E extends Comparable<E>> void sort2(E[] data){
        int h = data.length / 2;
        while (h >= 1){
            //堆 data[h, n), 进行插入排序
            for (int i = h; i < data.length; i++){
                E t = data[i];
                int j;
                for (j = i; j - h >= 0 && t.compareTo(data[j - h]) < 0; j -= h){
                    data[j] = data[j - h];
                }
                data[j] = t;
            }
        }
        h /= 2;
    }

    /**
     * 步长序列
     * @param data
     * @param <E>
     */
    public static <E extends Comparable<E>> void sort3(E[] data){
        int h = 1;
        while (h < data.length){
            h = h * 3 +1;
        }
        while (h >= 1){
            //堆 data[h, n), 进行插入排序
            for (int i = h; i < data.length; i++){
                E t = data[i];
                int j;
                for (j = i; j - h >= 0 && t.compareTo(data[j - h]) < 0; j -= h){
                    data[j] = data[j - h];
                }
                data[j] = t;
            }
        }
        h /= 3 ;
    }


    public static void main(String[] args) {
        int n = 1000000;

        Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);
        Integer[] arr3 = Arrays.copyOf(arr, arr.length);

        SortingHelper.sortTest("ShellSort", arr);
        SortingHelper.sortTest("ShellSort2", arr2);
        SortingHelper.sortTest("ShellSort3", arr3);
    }
}
